package cxydmmszl.chapter02.t021;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 两个链表生成相加链表
 * <li style="color: green;">Desc</li>
 * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 * 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
 * <li style="color: green;">Input</li>
 * 第一行两个整数 n 和 m，分别表示两个链表的长度。
 * 第二行 n 个整数 ai 表示第一个链表的节点。
 * 第三行 m 个整数 bi 表示第二个链表的节点。
 * <li style="color: green;">Output</li>
 * 输出一行整数表示结果链表。
 * <li style="color: blue;">Link</li> CD114
 *
 * @author habitplus
 * @since 2021-09-09 22:20
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return 0;
    }

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }
        Node head1 = genLinkedListByHead(arr);

        arr = new int[m];
        for (int i = 0; i < m; i++) {
            arr[i] = nextInt();
        }
        Node head2 = genLinkedListByHead(arr);

        Node ans = add(head1, head2);
        printLinkedList(ans);
    }

    private static Node add(Node head1, Node head2) {
        head1 = reverseList(head1);
        head2 = reverseList(head2);

        int k = 0;
        Node tou = null;
        Node node;

        while (head1 != null || head2 != null) {
            k += (head1 != null ? head1.val : 0);
            k += (head2 != null ? head2.val : 0);

            // 头插法
            node = tou;
            tou = new Node(k % 10);
            tou.next = node;
            k /= 10;
            head1 = head1 != null ? head1.next : null;
            head2 = head2 != null ? head2.next : null;
        }

        if (k > 0) {
            node = tou;
            tou = new Node(k);
            tou.next = node;
        }

        return tou;
    }

    private static Node reverseList(Node head) {
        Node pre = null;
        Node next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static Node genLinkedListByHead(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }

        Node next = null, node;
        for (int i = arr.length - 1; i >= 0; i--) {
            node = new Node(arr[i]);
            node.next = next;
            next = node;
        }

        return next;
    }

    public static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }
}
